#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    int InversePairs(vector<int> data) {
        vector<int> temp(data);
        int r = data.size() - 1;
        return InverseHelper(data, temp, 0, r);
    }

private:
    const int kmod = 1000000007;

    // Merge sort between indices l and r
    int InverseHelper(vector<int>& data, vector<int>& temp, int l, int r) {
        if (l>=r) return 0;
        
        int mid = (l+r) / 2;
        int count = 0;
        count += InverseHelper(data, temp, l, mid); count %= kmod;
        count += InverseHelper(data, temp, mid+1, r); count %= kmod;
        count += MergeAndCount(data, temp, l, mid, r); count %= kmod;
        
        return count;
    }
    
    // Assume both are sorted
    // Count the inversions across the middle line
    int MergeAndCount(vector<int>& data, vector<int>& temp, int left, int mid, int right) {
        int l1 = left, l2 = mid+1;
        int count = 0, i = 0;
        while (l1 <= mid && l2 <= right) {
            if (data[l1] <= data[l2]) {
                temp[i++] = data[l1++];
            } else {  // inversion!
                temp[i++] = data[l2++];
                count += (mid - l1 + 1);
                count %= kmod;
            }
        }
        while (l1 <= mid) temp[i++] = data[l1++];
        while (l2 <= right) temp[i++] = data[l2++];
        for (int k=0; k<i; k++) data[left+k] = temp[k];
        
        return count;
    }
};


int main() {
    Solution so;
    cout << so.InversePairs({4,3,2,1}) << endl;
    cout << so.InversePairs({1,2,3,4,5,6,7,0}) << endl;
    return 0;
}
